package cn.itsource.recursion;

/**
 *	递归：
 *		1. 概念：是一种思想。在方法内部调用自己的方法。（自己干自己）
 *		2. 作用：就是简化逻辑（循环）代码。
 *		3. 核心规律：
 *				1. 通过数值带入的方式，查找逻辑规律：
 *						就是有相似运算逻辑的代码，就是通过已知条件表示未知条件
 *				2. 通过条件判断（条件/循环）的方式，在满足条件的时候根据规律调用自己的方法。如果不满足就不会自己的方法，这就是出口
 *	
 *		4. 注意事项：
 *			1. 递归必须 有出口
 *			2. 能用循环用循环，不要用递归，因为效率极其低下。
 *			为什么效率低下？
 *				方法的调用都是创建新栈帧，入栈，而栈层级是有限制的
 *			StackOverflowError : 栈内存溢出错误。
 *
 *		5. 使用场景：
 *			1. 树状结构数据或者菜单结构的数据查询
 *			2. 有相似逻辑运算的结构
 *			3. 适用于层级结构少，数据量小的场景。（最重要）如果层级多，且数据量大用循环。
 *
 *		6. 解决了哪些问题：
 *			1. 汉诺塔
 *			2. 斐波拉契数列
 *			...
 */
public class RecursionTest3 {

	public static void main(String[] args) {
		//求1-n的和，用递归
		int sum = sum(5);
		System.out.println(sum);
		
	}
	
	/**
	 * 
	 * 求1-n的和
	 * 已知：
	 * 		核心规律：
 *				1. 通过数值带入的方式，查找逻辑规律：
 *						就是有相似运算逻辑的代码，就是通过已知条件表示未知条件（将所有的条件写出来）
 *				2. 通过条件判断（条件/循环）的方式，在满足条件的时候根据规律调用自己的方法。如果不满足就不会自己的方法，这就是出口
 *
	 * 		sum(1) = 1
	 * 		sum(2) = 3  => 1(sum(1)) + 2(n)
	 * 		sum(3) = 6  => 3(sum(2)) + 3(n)
	 * 		sum(4) = 10 => 6(sum(3)) + 4(n)
	 * 		sum(5) = 15 => 10(sum(1)) + 5(n)
	 */
	public static int sum(int n) {
		if (n == 1) {
			return 1;
		}else{
			return sum(n-1) + n;
		}
	}
	
}
